1. Field of the Invention
The present invention relates to a method and device of halftone imaging and more specifically to halftoning digitized grey value images divided into pixels.
2. Discussion of Related Art
A method of halftoning digitized grey value images is known from Ulichney, Robert: "Digital Halftoning, MIT Press, 1987, Chapter 8, under the name of error diffusion. In this, a grey value of a pixel is compared with a given threshold value. If this threshold value is exceeded a logic "one" or "zero" is generated. By means of this a binary printer, e.g. a black/white printer, can print the pixel as black or white. The error which occurs when a grey value is reduced to either black or white is known as the quantization error.
Apart from texts and lines, insofar as they do not contain grey tints, a quantization error of this kind will lead to an unacceptable result in the case of photographs and screens. However, by dividing the quantization error over and adding it to grey values of neighboring pixels which have not yet been thresholded, a grey value impression perceived by the eye to correspond to the grey value before thresholding will nevertheless be obtained despite the fact that there are only two values to print. A grey surface whose grey value is, for example, approximately equal to the threshold value will, as a result, be converted to a mixture of approximately as many black as white pixels which, over a larger area, will give the same grey value impression as that of the original grey surface.
FIG. 1A shows the general principle of an error diffusion method. A digitized grey value l(n) corresponding to the grey value of a pixel n of an image divided into pixels is subjected to a first threshold processing 1. In this case, the digitized grey value l(n) may consist, for example, of an 8-bit data word with which 256 possible grey values of a pixel can then be reproduced. It should be noted that the term "grey value" in this context is not intended to indicate the color grey but an intensity value. The "grey value" can thus also refer to a color of a color separation image of a color image made up of elementary colors such as cyan, magenta and yellow. The grey value l(n) may originate, for example, from a document scanner, an image memory or a communications line. Finally, the pixels will frequently be arranged in horizontal lines and vertical columns with, for example, 300 pixels per inch or 600 pixels per inch.
The threshold processing 1 usually consists of a comparison of the grey value information l(n) with a fixed threshold value T. For example, T=128 in the case of 8-bit grey value information. However, without departing from the error diffusion principle, different location-dependent threshold values can be applied. These can be obtained, for example, by means of a dither matrix.
After thresholding of the grey value l(n), the result O(n) will be "0" (black) or "1" (white, color) depending on whether the grey value l(n) is less than or greater than the threshold value T. This result is suitable for supplying to a binary printer or reproduction system, e.g. a black/white printing laser or LED printer. It should be noted that halftoning is not restricted solely to converting grey value signals to binary signals. Halftoning can also be used, for example, for converting 8-bit grey value signals to 4-bit grey value signals. A difference, hereinafter referred to as a quantization error, between the grey value l(n) and the binary value O(n), obtained by thresholding of a pixel n, is determined in a rounding-off error determining step 2 and divided, by a dividing operation 3, and added, via adding step 4, to the next grey values l(n+1),l(n+2), . . . still to be thresholded.
Depending on the pixels over which, and the weighting factors with which, the quantization error is transported, a specific error diffusion method is obtained. In the above-mentioned work by Ulichney, various methods are described for dividing and adding or transporting the quantization error. For example, according to Floyd and Steinberg, transport to 4 neighboring pixels is applied, or, according to Jarvis, Judice and Ninke, transport to 12 neighboring pixels. In these cases, the quantization error is transported to the neighboring pixels with different weighting factors.
FIG. 1B gives an example of transportation of the quantization error according to Floyd and Steinberg. The quantization error of the thresholded pixel n indicated by a dot is transported, with the weighting factors indicated in the Figure, to the following pixel n+1 on the same image line and to the pixels n+m, n+m+1, n+m+2 on a following image line. The thresholding sequence is indicated by a given path formed, for example, by a line raster, the lines of which are successively traversed from left to right and from top to bottom. Various error diffusion methods are obtained inter alia by the choice of pixels to which the quantization error is transported, the weighting factors with which this is done, and the choice of path.
One disadvantage of the method according to the error diffusion principle is the visibility of regular tracks of successive pixels having the same grey value in the print. Such tracks occur as a result of the transportation of the quantization error in accordance with a fixed distribution. Accordingly, it is known to suppress these regular tracks to some extent, for example by providing a random fluctuating component for the weighting factors with which the quantization errors are divided.
Other likewise known methods of suppressing such tracks are based on a less regular path by which the pixels are successively processed. For example the pixels may be processed in accordance with a serpentine-like path, in which the pixels are traversed alternately line-wise from left to right and vice-versa. Thus FIG. 1C, for example, illustrates a serpentine path 5, in which the pixels n, n+1 . . . are processed alternately from left to right and from right to left. The pixels are therefore thresholded consecutively one by one in the sequence n, n+1, . . . n+m, n+m+1 . . . etc. In this way the occurrence of "tracks" as a result of the transmission of errors in the same direction is suppressed to a certain extent.
Another example is a path traversing a pseudo-random curve such as meander-shaped Hilbert or Peano-curve. FIG. 2 gives an example of such a path 6 as described by I. A. Witten and R. M. Neal in "Using Peano Curves for Bilevel Display of Continuous Tone Images" (IEEE Computer Graphics & Applications; May (1982), pages 47-52). A path of this kind also traverses all the pixels in which the pixels are thresholded consecutively one by one. A quantization error from a pixel n is in this case transported over the next pixel n+1 on the curve. As a result, the distribution of the quantization error also acquires a quasi-random character. The instant literature also describes dividing an image into different parts each traversed by a Peano-curve. In this case, however, the quantization error of a pixel is always transported to a pixel of the same curve.
A disadvantage of pseudo-random curves of this kind is that the reproduction of spatial details is reduced since the quantization error is now always distributed in changing directions, as noted by G. S. Fawcett and G. F. Schrack in "Halftoning Techniques Using Error Correction" (Proceedings of the SID, 27, (1986), pages 305-308).
Another disadvantage of halftoning methods based on error diffusion is the serial character. For example, a pixel at the end of a scanning line cannot be processed until the pixels in front of it on the scanning line have been processed so that the quantization error to be added to the pixel is available. Consequently, this method is less suitable for a simultaneous and parallel processing of pixels. Although the processing time can be reduced by dividing an image into different sub-images, each of which is subjected to an error diffusion processing operation separately by means of its own path, the boundaries between the sub-images will still remain visible. The sub-images must also have minimum dimensions for good distribution of the quantization error.